package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         222,
		Discription: "完全二叉的节点个数",
		Level:       1,
		Labels: map[string]int{
			"递归": 1,
		},
	})
}

func CountNodes(root *ds.TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := depth(root.Left)
	rigthDepth := depth(root.Right)
	if leftDepth == rigthDepth {
		//左子树必是满二叉，右子树可能是满二叉
		return 1<<leftDepth + CountNodes(root.Right)
	} else {
		//左子树必不是满二叉，右子树必须是满二叉
		return CountNodes(root.Left) + 1<<rigthDepth
	}
}

func depth(node *ds.TreeNode) int {
	count := 0
	//找最深的节点，所以是遍历左节点，完全二叉树无需遍历左右子树选最深的
	for node != nil {
		count++
		node = node.Left
	}

	return count
}
